/**
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 * 两个相邻元素间的距离为 1 。
 * 
 * TIPS：图的DFS/BFS(树和图的两大区别：1、一个单源一个多源；2、tree是有向的不用标记是否访问过，但无向图必须标记，并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问)
 * 将1到0的距离转换成求0到1的距离
 */

#include<vector>
#include<queue>
using namespace std;

/**
 * Solution 1:BFS
 * 首先把每个源点 0入队，然后从各个 0同时开始一圈一圈的向 1 扩散（每个 1都是被离它最近的 0扩散到的 ）
 * 扩散的时候可以设置 int[][] dist 来记录距离（即扩散的层次）并同时标志是否访问过。
 * 对于本题是可以直接修改原数组 int[][] matrix 来记录距离和标志是否访问的
 * 把 matrix 数组中 1 的位置设置成 -1、Integer.MAX_VALUE、m * n、10000都行，只要是个无效的距离值来标志这个位置的 1 没有被访问过就行
 */
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        // 矩阵维度
        int m = mat.size();
        int n = mat[0].size();

        // 四个方向
        vector<pair<int,int>> around = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        // 存放距离的矩阵，距离初始设为MAX
        vector<vector<int>> dist(m, vector<int>(n, __INT_MAX__));
        // BFS使用队列
        queue<pair<int,int>> que;

        // 将所有的0加入初始队列中，并把他们的距离结果0填入矩阵
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j] == 0){
                    dist[i][j] = 0;
                    que.push({i,j});
                }
            }
        }

        // BFS
        while(!que.empty()){
            // auto在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型
            // NOTICE:auto 变量必须在定义时初始化，这类似于const关键字。
            auto head = que.front();
            que.pop();
            // 对队首元素的四个方向元素依此进行计算
            for(int k=0; k<4; k++){
                int x = head.first + around[k].first;
                int y = head.second + around[k].second;
                // 判断这些周围点在不在矩阵范围内
                if(x>=0 && x<m && y>=0 && y<n){
                    // 周围节点到0的距离应该是当前节点到0的距离+1，如果大于这个数就应该更新结果矩阵
                    if(dist[x][y] > dist[head.first][head.second]+1){
                        dist[x][y] = dist[head.first][head.second]+1;
                        que.push({x,y});
                    }
                }
            }
        }

        return dist;
    }
};


/**
 * Solution 2:动态规划
 * 对于任一点 (i, j)(i,j)，距离 0 的距离为：
 * f(i, j) = 1 + min(f(i-1, j), f(i, j-1), f(i+1, j), f(i, j+1)) if matrix[i][j] == 1
 *           0                                                   if matrix[i][j] == 0
 * 因此我们用 dp[i][j]来表示该位置距离最近的 0的距离。 dp[i][j] 是由其上下左右四个状态来决定
 * 
 * 将问题分解:
 * 1.距离 (i, j)最近的 0 的位置，是在其 「左上，右上，左下，右下」4个方向之一；
 * 2.分别从四个角开始递推，就分别得到了位于「左上方、右上方、左下方、右下方」距离 (i, j) 的最近的 0的距离，取 min即可；
 * 3.通过上两步思路，我们可以很容易的写出 4个双重 for 循环，动态规划的解法写到这一步其实已经完全 OK了
 * 从四个角开始的 44 次递推，其实还可以优化成从任一组对角开始的 22 次递推，比如只写从左上角、右下角开始递推就行了
 */
class Solution_2 {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
        vector<vector<int>> dist(m, vector<int>(n, __INT_MAX__ / 2));
        // 如果 (i, j) 的元素为 0，那么距离为 0
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) {
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        return dist;
    }
};